The present embodiments relate to image processing.
Image convolution is an operator used in digital image processing. Convolution is useful in, for example, image smoothing, edge detection, and correlation. Convolution may be represented as follows:
            I      out        ⁡          (              x        ,        y            )        =            ∑              i        =        0            m        ⁢                  ∑                  j          =          0                n            ⁢                                    I                          i              ⁢                                                          ⁢              n                                ⁡                      (                                          x                -                                  n                  /                  2                                +                j                            ,                              y                -                                  m                  /                  2                                +                i                                      )                          ⁢                  K          ⁡                      (                          i              ,              j                        )                              where Iin, Iout, and K are the input, convolved and kernel images, respectively, where m and n are the dimensions of the kernel image. The algorithm complexity of a direct implementation of the image convolution operator using a moving window is in the order of m×n×l×o, where l and o denote the dimensions of the input and convolved images. To reduce the computation cost, techniques such as multi-thread programming are employed, when the dimension of the image or the kernel is large.
For a separable kernel, defined as K(x,y)=KH(x)KV(y), the two-dimensional image convolution operation may be efficiently implemented by applying the horizontal kernel, KH(x), and the vertical kernel, KV(y), separately. The one-dimensional horizontal kernel is applied to each row of the image and the result is a row-smoothed image Ih. The one-dimensional vertical kernel is then applied to each column of the row-smoothed image Ih. The algorithm complexity for separable kernels is thus simpler, and on the order of m×l×n+m×n×o. The dimension complexity is greatly reduced relative to direct implementation using a moving two-dimensional window.
Unfortunately, not all two-dimensional kernels are separable.